#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define TRUE 1
#define FALSE 0

typedef struct Node {
	int data;
	struct Node* next;
}Node;
typedef struct TreeNode {
	int data;
	struct TreeNode* lchild;
	struct TreeNode* rchild;
}TreeNode;



//功能菜单
void menu();
//初始化单链表
Node* initList();
//创建一个大规模无重复元素的集合（单链表）
Node* createGather(Node* L);
//判断data是否在单链表L中
int has(Node* L, int data);
//采用头插法向集合中插入元素
void headInsert(Node* L, int data);
//采用尾插法向集合中插入元素
void tailInsert(Node* L, int data);
//删除单链表中的元素（按值删除）
int delete(Node* L, int data);
//利用二叉排序树中序遍历 排序单链表L(目标集合)
Node* sortList(Node* L);
//顺序查找集合中的元素
Node* findNode(Node* L, int data);
//去除集合中的重复元素（在创建一个大规模无重复元素的集合中调用）
Node* removeDuplicate(Node* L);
//对两个集合求并集
Node* Union(Node* L1, Node* L2);
//对两个集合求交集
Node* Intersection(Node* L1, Node* L2);
//对两个集合求差集
Node* Difference(Node* L1, Node* L2);
//判断L1是否是L2的子集（对两个集合求补集中调用）
int isSubSet(Node* l1, Node* l2);
//对两个集合求补集
Node* complement(Node* L1, Node* L2);
//求集合的势
int card(Node* L);
//top-k问题
int topK(Node* L, int k);
//输出链表中的所有元素
void printList(Node* L);
//中序遍历二叉排序树
void inOrder(TreeNode* T, Node* L);
//插入元素到二叉排序树排序树
void bstInsert(TreeNode** T, int data);
//利用已有链表创建二叉排序树
TreeNode* createTree(Node* L);




int main() {
	Node* L1 = initList();
	Node* L2 = initList();
	Node* L3 = initList();
	Node* L4 = initList();
	Node* L5 = initList();
	Node* L6 = initList();
	Node* findnode = NULL;//存放查找函数的结果
	int choice;//定义操作的集合为此
	int option;//定义功能选择数为此
	int data;//定义插入的数据为此
	int k;// top - k的k值为此
	while (1) {
		menu();
		scanf("%d", &option);

		switch (option) {
		case 0:
			exit(0);
			break;
		case 1:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n");
			scanf("%d", &choice);
			if (choice == 1) { createGather(L1); printf("创建集合L1成功！\n"); }
			else if (choice == 2) {
				createGather(L2); printf("创建集合L2成功！\n");
			}
			else return printf("输入错误！\t （输入样例：1 对应 L1 ，2 对应 L2 。)");
			break;
		case 2:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n ");
			scanf("%d", &choice);
			switch (choice) {
			case 1:
				printList(L1);
				printf("集合L1显示完毕！\n");
				break;
			case 2:
				printList(L2);
				printf("集合L2显示完毕！\n");
				break;
			case 3:
				printList(L3);
				printf("集合L3显示完毕！\n");
				break;
			case 4:
				printList(L4);
				printf("集合L4显示完毕！\n");
				break;
			case 5:
				printList(L5);
				printf("集合L5显示完毕！\n");
				break;
			case 6:
				printList(L6);
				printf("集合L6显示完毕！\n");
				break;
			default:
				printf("无效显示操作！");
			}
			break;
		case 3:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n ");
			scanf("%d", &choice);
			printf("请输入插入元素值：");
			scanf("%d", &data);
			switch (choice) {
			case 1:
				headInsert(L1, data);
				printf("元素插入集合L1完毕！\n");
				break;
			case 2:
				headInsert(L2, data);
				printf("元素插入集合L2完毕！\n");
				break;
			case 3:
				headInsert(L3, data);
				printf("元素插入集合L3完毕！\n");
				break;
			case 4:
				headInsert(L4, data);
				printf("元素插入集合L4完毕！\n");
				break;
			case 5:
				headInsert(L5, data);
				printf("元素插入集合L5完毕！\n");
				break;
			case 6:
				headInsert(L6, data);
				printf("元素插入集合L6完毕！\n");
				break;
			default:
				printf("无效插入操作！");
			}
			break;
		case 4:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n ");
			scanf("%d", &choice);
			printf("请输入删除元素值：");
			scanf("%d", &data);
			switch (choice) {
			case 1:
				delete(L1, data);
				printf("集合L1中目标元素删除完毕！\n");
				break;
			case 2:
				delete(L2, data);
				printf("集合L2中目标元素删除完毕！\n");
				break;
			case 3:
				delete(L3, data);
				printf("集合L3中目标元素删除完毕！\n");
				break;
			case 4:
				delete(L4, data);
				printf("集合L4中目标元素删除完毕！\n");
				break;
			case 5:
				delete(L5, data);
				printf("集合L5中目标元素删除完毕！\n");
				break;
			case 6:
				delete(L6, data);
				printf("集合L6中目标元素删除完毕！\n");
				break;
			default:
				printf("无效删除操作！");
			}
			break;
		case 5:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n ");
			scanf("%d", &choice);
			switch (choice) {
			case 1:
				L1= sortList(L1);
				printf("集合L1排序完毕！\n");
				break;
			case 2:
				L2=sortList(L2);
				printf("集合L2排序完毕！\n");
				break;
			case 3:
				L3=sortList(L3);
				printf("集合L3排序完毕！\n");
				break;
			case 4:
				L4=sortList(L4);
				printf("集合L4排序完毕！\n");
				break;
			case 5:
				L5 = sortList(L5);
				printf("集合L5排序完毕！\n");
				break;
			case 6:
				L6=sortList(L6);
				printf("集合L6排序完毕！\n");
				break;
			default:
				printf("无效排序操作！");
			}
			break;
		case 6:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2 。):\n ");
			scanf("%d", &choice);
			printf("请输入查找元素值：");
			scanf("%d", &data);
			switch (choice) {
			case 1:
				findnode = findNode(L1, data);
				printf("集合L1中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			case 2:
				findnode = findNode(L2, data);
				printf("集合L2中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			case 3:
				findnode = findNode(L3, data);
				printf("集合L3中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			case 4:
				findnode = findNode(L4, data);
				printf("集合L4中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			case 5:
				findnode = findNode(L5, data);
				printf("集合L5中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			case 6:
				findnode = findNode(L6, data);
				printf("集合L6中目标元素查找完毕！（使用findnode保存地址）\n");
				break;
			default:
				printf("无效查找操作！");
			}
			break;
		case 7:
			L3 = Union(L1, L2);
			printf("求并集完成！(已存入L3中）\n");
			break;
		case 8:
			L4 = Intersection(L1, L2);
			printf("求交集完成！(已存入L4中）\n");
			break;
		case 9:
			L5 = Difference(L1, L2);
			printf("求差集完成！(已存入L5中）\n");
			break;
		case 10:
			L6 = complement(L1, L2);
			printf("求补集完成！(已存入L6中）\n");
			break;
		case 11:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2...6 对应 L6):\n ");
			scanf("%d", &choice);
			switch (choice) {
			case 1:
				printf("集合L1的势为 ： %d\n", card(L1));
				break;
			case 2:
				printf("集合L2的势为 ： %d\n", card(L2));
				break;
			case 3:
				printf("集合L2的势为 ： %d\n", card(L3));
				break;
			case 4:
				printf("集合L2的势为 ： %d\n", card(L4));
				break;
			case 5:
				printf("集合L2的势为 ： %d\n", card(L5));
				break;
			case 6:
				printf("集合L2的势为 ： %d\n", card(L6));
				break;
			default:
				printf("无效求集合L%d操作！", choice);
			}
			break;
		case 12:
			printf("请输入操作对象（输入样例：1 对应 L1 ，2 对应 L2...6 对应 L6):\n ");
			scanf("%d", &choice);
			printf("请输入k的值：\n ");
			scanf("%d", &k);
			switch (choice) {
			case 1:
				printf("集合L1的top-%d为 ： %d\n", k, topK(L1, k));
				break;
			case 2:
				printf("集合L2的top-%d为 ： %d\n", k, topK(L2, k));
				break;
			case 3:
				printf("集合L3的top-%d为 ： %d\n", k, topK(L3, k));
				break;
			case 4:
				printf("集合L4的top-%d为 ： %d\n", k, topK(L4, k));
				break;
			case 5:
				printf("集合L5的top-%d为 ： %d\n", k, topK(L5, k));
				break;
			case 6:
				printf("集合L6的top-%d为 ： %d\n", k, topK(L6, k));
				break;
			default:
				printf("无效求top-k操作！\n");
			}
			break;
		default:
			printf("无效操作！");
		}

	}

}








//初始化单链表
Node* initList() {
	Node* L = (Node*)malloc(sizeof(Node));
	L->data = 0;
	L->next = NULL;
	return L;
}

//随机生成一个不同规模的数据集（线性表） 0~32767

Node* createGather(Node* L) {
	int randnum;
	srand((unsigned)time(0));
	int maxNum = rand() % RAND_MAX;
	for (int i = 0; i < maxNum; i++) {
		randnum = rand() % RAND_MAX;
		headInsert(L, randnum);
	}
	//L = removeDuplicate(L);
	return L;
}

//判断元素在集合中是否已经存在
int has(Node* L, int data) {

	while (L) {
		if (L->data == data) {
			return 1;
		}
		L = L->next;

	}
	return 0;
}

//头插法插入元素
void headInsert(Node* L, int data) {
	if (has(L, data)) return;
	Node* node = (Node*)malloc(sizeof(Node));
	node->data = data;
	node->next = L->next;
	L->next = node;
	L->data++;
}

//尾插法插入元素
void tailInsert(Node* L, int data) {
	if (has(L, data)) return;
	Node* node = L;
	for (int i = 0; i < L->data; i++) {
		node = node->next;
	}
	Node* n = (Node*)malloc(sizeof(Node));
	n->data = data;
	n->next = NULL;
	node->next = n;
	L->data++;
}

//删除集合中的元素（按值删除）
int delete(Node* L, int data) {
	Node* preNode = L;
	Node* node = L->next;
	while (node) {
		if (node->data == data) {
			preNode->next = node->next;
			free(node);
			L->data--;
			return TRUE;
		}
		preNode = node;
		node = node->next;
	}
	return FALSE;
}


//查找(顺序查找）返回位置
Node* findNode(Node* L, int data) {

	if (!has(L, data)) {
		return NULL;
	}
	else {
		while (L->data != data) {
			L = L->next;
		}
	}
	return L;
}

//去重
Node* removeDuplicate(Node* L) {
	Node* cur = L;
	Node* pre = NULL;
	Node* next = NULL;

	while (cur) {
		pre = cur;
		next = cur->next;

		while (next) {
			if (cur->data == next->data) {
				pre->next = next->next;
				L->data--;
			}
			else {
				pre = next;
			}
			next = next->next;
		}
		cur = cur->next;
	}
	return L;
}

//并集
Node* Union(Node* L1, Node* L2) {
	Node* L3 = initList();
	while (L1) {
		tailInsert(L3, L1->data);
		L1 = L1->next;
	}
	while (L2) {
		tailInsert(L3, L2->data);
		L2 = L2->next;

	}
	return removeDuplicate(L3);

}

//交集
Node* Intersection(Node* L1, Node* L2) {
	Node* L3 = initList();
	if (L1->data < L2->data) {
		for (int i = 0; i < L1->data; i++) {
			if (has(L2, L1->data))
				tailInsert(L3, L1->data);
			L1 = L1->next;
		}
	}
	else {
		for (int i = 0; i < L2->data; i++) {
			if (has(L1, L2->data))
				tailInsert(L3, L2->data);
			L2 = L2->next;
		}

	}
	return L3;
}

//差集
Node* Difference(Node* L1, Node* L2) {
	Node* L3 = initList();
	if (L1->data > L2->data) {
		for (int i = 0; i < L1->data; i++) {
			if (!has(L2, L1->data))
				tailInsert(L3, L1->data);
			L1 = L1->next;
		}
	}
	else {
		for (int i = 0; i < L2->data; i++) {
			if (!has(L1, L2->data))
				tailInsert(L3, L2->data);
			L2 = L2->next;
		}

	}
	return removeDuplicate(L3);
}

//判断L1,是否为L2 的子集
int isSubSet(Node* l1, Node* l2) {
	while (l1) {
		if (!has(l2, l1->data)) return FALSE;
		l1 = l1->next;
	}
	return TRUE;
}
// 补集
Node* complement(Node* L1, Node* L2) {
	Node* L3 = initList();
	if (isSubSet(L1, L2)) {
		L2 = L2->next;
		while (L2) {
			if (!has(L1, L2->data)) {
				tailInsert(L3, L2->data);

			}
			L2 = L2->next;
		}
	}
	else if (isSubSet(L2, L1)) {
		L1 = L1->next;
		while (L1) {
			if (!has(L2, L1->data)) {
				tailInsert(L3, L1->data);
			}
			L1 = L1->next;
		}
	}
	else {
		return NULL;
	}

	return L3;
}

// 势
int card(Node* L) {
	return L->data;
}

//top-k
int topK(Node* L, int k) {
	int length = L->data;
	L = sortList(L);
	//printf("length = %d\n", L->data);
	int target = length - k+1;
	//printf("%d\n", target);
	for (int i = 0; i < target; i++) {
		L = L->next;
	}return L->data;
}

//遍历输出所有元素
void printList(Node* L) {
	if (!L) { printf("集合为空！\n"); return; }
	Node* node = L->next;
	int n = 0;
	while (node) {
		printf("node%d = %d\n", ++n, node->data);
		node = node->next;
	}
}
//菜单
void menu()
{
	printf("************单链表集合运算************\n\n");
	printf("\t1.创建集合\n\n");
	printf("\t2.集合数据显示\n\n");
	printf("\t3.向集合中插入元素\n\n");
	printf("\t4.删除集合中的元素\n\n");
	printf("\t5.对集合进行排序\n\n");
	printf("\t6.查找集合中的元素\n\n");
	printf("\t7.求集合L1和集合L2的并集\n\n");
	printf("\t8.求集合L1和集合L2的交集\n\n");
	printf("\t9.求集合L1和集合L2的差集\n\n");
	printf("\t10.求集合L1和集合L2的补集\n\n");
	printf("\t11.求集合的势\n\n");
	printf("\t12.求top-k问题\n\n");

	printf("\t0.退出系统\n\n");
	printf("************单链表集合运算************\n");
	printf("请输入选项:");
}

//插入元素到二叉排序树排序树
void bstInsert(TreeNode** T, int data) {
	if (*T == NULL) {
		*T = (TreeNode*)malloc(sizeof(TreeNode));
		(*T)->data = data;
		(*T)->lchild = NULL;
		(*T)->rchild = NULL;
	}
	else if (data == (*T)->data) {
		return;
	}
	else if (data < (*T)->data) {
		bstInsert(&((*T)->lchild), data);
	}
	else {
		bstInsert(&((*T)->rchild), data);
	}
}

//利用已有链表创建二叉排序树

TreeNode* createTree(Node* L) {
	TreeNode* T = NULL;
	while (L) {
		bstInsert(&T, L->data);
		L = L->next;
	}
	return T;
}
//中序遍历二叉排序树
void inOrder(TreeNode* T, Node* L) {
	if (T) {
		inOrder(T->lchild, L);
		tailInsert(L, T->data);
		inOrder(T->rchild, L);
	}
}
//利用链表构造二叉排序树，中序遍历二叉排序树得到升序
Node* sortList(Node* L) {
	TreeNode* T = createTree(L);
	Node* nodes = initList();
	inOrder(T, nodes);
	return nodes;
}
